package sort.onlogn;

/**
 * 归并排序：先把数组从中间分成前后两部分，然后对前后两部分分别排序，
 * 再将排好序的两部分合并在一起，这样整个数组就都有序了
 * <p>
 * 稳定非原地排序
 *
 * @author yeyangtao created at 10:40 2020/9/27
 */
public class MergeSort {
    public static void mergeSort(int[] a) {
        int size = a.length;
        mergeSortInternally(a, 0, size - 1);
    }

    private static void mergeSortInternally(int[] a, int p, int r) {
        if (p >= r) return;
        //取中间,防止r+p超过int最大值
        int q = p + (r - p) / 2;
        //分治递归
        mergeSortInternally(a, p, q);
        mergeSortInternally(a, q + 1, r);
        //将A[p...q]和A[q+1...r]合并为A[p...r]
        mergeBySentry(a, p, q, r);
    }

    /**
     * 将A[p...q]和A[q+1...r]合并为A[p...r]
     */
    private static void merge(int[] a, int p, int q, int r) {
        int[] temp = new int[a.length];
        int i = p, j = q + 1, k = 0;
        //用i，j分别表示A[p...q]和A[q+1...r]数组的起始下标
        //哪个小就加入到temp中，并向后移动
        while (i <= q && j <= r) {
            if (a[i] <= a[j]) temp[k++] = a[i++];
            else temp[k++] = a[j++];
        }
        //判断那个子数组有剩余数据
        int start = i, end = q;
        if (j <= r) {
            start = j;
            end = r;
        }
        //把剩余数据加到temp中
        for (; start <= end; start++) {
            temp[k++] = a[start++];
        }
        //将tmp中的数组拷贝回A[p...r]
//        for (int ii = 0; ii < r - p; ii++) {
//            a[p + ii] = temp[ii];
//        }
        if (r - p > 0)
            System.arraycopy(temp, 0, a, p, r - p);
    }

    /**
     * 采用哨兵的思想
     * 将A[p...q]和A[q+1...r]合并为A[p...r]
     */
    private static void mergeBySentry(int[] a, int p, int q, int r) {
        int[] left = new int[q - p + 2];
        int[] right = new int[r - q + 1];
        //添加到临时数组
        if (q - p + 1 >= 0)
            System.arraycopy(a, p, left, 0, q - p + 1);
//        for (int i = 0; i <= q - p; i++) {
//            left[i] = a[p + i];
//        }
        //第一个数组添加哨兵
        left[q - p + 1] = Integer.MAX_VALUE;

        if (r - q > 0)
            System.arraycopy(a, q + 1, right, 0, r - q);
        //        for (int i = 0; i <= r - q - 1; i++) {
//            right[i] = a[q + 1 + i];
//        }

        //第二个数组添加哨兵
        right[r - q] = Integer.MAX_VALUE;

        int i = 0, j = 0, k = p;
        while (k <= r) {
            if (left[i] <= right[j])
                a[k++] = left[i++];
            else
                a[k++] = right[j++];
        }
    }
}
